#include <bits/stdc++.h>

using namespace std;

// 返回链表的第一个入环节点
// 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/

// 不需要提交这个类
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 提交这个类即可
class Solution
{
public:
    ListNode *detectCycle(ListNode *head) 
    {
        if(!head || !head->next || !head->next->next) return nullptr;
        ListNode *slow = head->next, *fast = head->next->next;
        while(slow != fast)
        {
            if(!fast->next || !fast->next->next) return nullptr;
            slow = slow->next;
            fast = fast->next->next; 
        }
        fast = head;
        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};


// 提交这个类即可
class Solution 
{
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode *slow = head, *fast = head;
        // 慢指针一次走一步，快指针一次走两步
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇
            if(slow == fast)
            {
                // 慢指针回到头结点，快慢指针都每次走一步
                // 快慢指针再次相遇就是第一个入环节点
                slow = head; 
                while(slow != fast)
                {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        // 快指针走到空节点，那么就一定没有环
        return nullptr;
    }
};